package com.lucien.Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class InsertSort {
    public static void main(String[] args) {
        int [] arr = {101,34,119,1,-1,20,30};

//        insertSort(arr);

        insertSort1(arr);
        System.out.println(Arrays.toString(arr));
//
//        insertSort2(arr);
//        System.out.println(Arrays.toString(arr));

    }

    /**
     * 分步实现
     * @param arr
     */
    public static void insertSort(int [] arr){
        //定义待插入的数
        int insertVal = arr[1];
        int insertindex = 1-1;//insertVal前一个数的下标

        /**
         *  insertindex >= 0 保证插入的数字不越界
         *  insertVal < arr[insertindex] 待插入的数还没有找到要插入的位置
         *  需要将arr[insertindex]后移
         */
        while (insertindex >= 0 && insertVal < arr[insertindex] ) {
            arr[insertindex + 1] = arr[insertindex];
            insertindex--;
        }
        //当退出while循环时，说明插入的位置找到，insertindex + 1
        arr[insertindex+1] = insertVal;

        System.out.println("第一轮");
        System.out.println(Arrays.toString(arr));


        insertVal = arr[2];
        insertindex = 2-1;//insertVal前一个数的下标
        while (insertindex >= 0 && insertVal < arr[insertindex] ) {
            arr[insertindex + 1] = arr[insertindex];
            insertindex--;
        }
        //当退出while循环时，说明插入的位置找到，insertindex + 1
        arr[insertindex+1] = insertVal;

        System.out.println("第二轮");
        System.out.println(Arrays.toString(arr));

        insertVal = arr[3];
        insertindex = 3-1;//insertVal前一个数的下标
        while (insertindex >= 0 && insertVal < arr[insertindex] ) {
            arr[insertindex + 1] = arr[insertindex];
            insertindex--;
        }
        //当退出while循环时，说明插入的位置找到，insertindex + 1
        arr[insertindex+1] = insertVal;

        System.out.println("第三轮");
        System.out.println(Arrays.toString(arr));
    }

    //小 -> 大
    public static void insertSort1(int [] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertindex = i - 1;
            while (insertindex >= 0 && insertVal < arr[insertindex]) {
                arr[insertindex + 1] = arr[insertindex];
                insertindex--;
            }
            if (insertindex + 1 != i){
                arr[insertindex+1] = insertVal;
            }
            System.out.println("第"+i+"轮");
            System.out.println(Arrays.toString(arr));
        }
    }

    //大 -> 小
    public static void insertSort2(int [] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertindex = i - 1;
            while (insertindex >= 0 && insertVal > arr[insertindex]) {
                arr[insertindex + 1] = arr[insertindex];
                insertindex--;
            }
            if (insertindex + 1 != i){
                arr[insertindex+1] = insertVal;
            }
//            System.out.println("第"+i+"轮");
//            System.out.println(Arrays.toString(arr));
        }
    }
    public static void testTime(){
        int [] arr = new int [80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String str1 = simpleDateFormat.format(date1);
        System.out.println("排序前的时间是："+date1);

        insertSort1(arr);

        Date date2 = new Date();
        String str2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间是："+date2);
    }

}
